package com.algorithm.array;

/**
 * Created by dongxie on 2021/12/8.
 * https://leetcode-cn.com/problems/binary-search/
 */
public class BinarySearch {
    public static void main(String[] args) {

    }

    /**
     * 第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
     * 区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
     * ● while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
     * ● if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) {  // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1;  // target 在右区间，所以[middle + 1, right]
            } else {
                return middle;// 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }


}
